package mao.leetcode.dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Totoro
 * @date 2020/5/28
 * @explain:题目：给定一组码子，码子长度相同，只有一个字符不同的码字之间相互连接
 *         给出从指码字到指定目标码字之间最短的路径。
 */
public class Solution {
    private boolean visited[];
    private int source,target;
    private List<Integer> path = new LinkedList<>();
    int num;
    boolean[][] adjacency = new boolean[num][num];

    public LinkedList<String> getMIn(int num, ArrayList<String> players,String source,String target){

        visited = new boolean[num];
        this.num = num;

        for (int i = 0; i < players.size(); i++) {
            String player_1 = players.get(i);
            if (source.equals(player_1)) this.source = i;
            if (target.equals(player_1)) this.target = i;
            for (int j = i+1; j < players.size(); j++) {
                if (check(player_1,players.get(j))){
                    adjacency[i][j] = true;
                    adjacency[j][i] = true;
                }
            }
        }
        dfs(this.source,new LinkedList<>());

        if (path == null) return null;
        LinkedList<String> res = new LinkedList<>();
        for (int i = 0; i < path.size();i++) {
            res.add(players.get(path.get(i)));
        }
        return res;
    }

   public void dfs(int i,LinkedList<Integer> list ){
        if (visited[i]) return;
        visited[i] = true;
        list.add(i);

        if(i == target){
            if (path ==  null || list.size() < path.size()){
                path = new LinkedList<>(list);
            }
        }
       for (int j = 0; j < num; j++) {
           if (adjacency[i][j]){
               dfs(j,list);
           }
       }

       list.removeLast();
       visited[i] = false;
   }

   public boolean check(String s_1,String s_2){
       char[]  chars_1 = s_1.toCharArray();
       char[] chars_2 = s_2.toCharArray();
       int count = 0;
       for (int i = 0; i < chars_1.length; i++) {
           if((chars_1[i]^chars_2[i]) != 0){
               count++;
               if (count >=2){
                   return false;
               }
           }
       }
       if (count == 1) return true;
       else return false;
   }
}
